//1.前序遍历递归--空间复杂度O(n)

class Solution {
public:
    vector<TreeNode*> temp;
    void preorder_tree(TreeNode* root) {
        if(root==nullptr) return;
        temp.push_back(root);
        preorder_tree(root->left);
        preorder_tree(root->right);
        return;
    }

    void flatten(TreeNode* root) {
        preorder_tree(root);
        int _size = temp.size();
        for(int i=1;i<_size;++i) {
            TreeNode* prev = temp[i-1];
            
            prev->left = nullptr;
            prev->right = temp[i];
        }

        return;
    }
};

//2.原地修改-----O(1)----Morris Traversal
/*
root右子树遍历的时候，肯定已经遍历完root节点和root左子树了，root左子树的最后一个元素遍历完后，才开始遍历root右子树的第一个节点
所以我们把root右子树的第一个节点，放到root左子树的最后一个元素之后，这样遍历顺序还是不变。然后root新的右子树就是旧的root左子树，root新的左子树就是nullptr,挨个迭代
*/
class Solution {
public:
    void flatten(TreeNode* root) {
        if(root==nullptr) return;

        TreeNode* curr = root;
        while(curr) {
            if(curr->left) {
                TreeNode* act = curr->left;
                while(act->right) {
                    act = act->right;
                }
                act->right = curr->right;
                curr->right = curr->left;
                curr->left = nullptr;

            }
            curr= curr->right;
        }

        return;
    }
};

/*
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* curr = root;
        while (curr) {
            if (curr->left) {
                // 找到左子树的最右节点（前驱）
                TreeNode* predecessor = curr->left;
                while (predecessor->right) {
                    predecessor = predecessor->right;
                }
                // 将原右子树接到前驱节点的右边
                predecessor->right = curr->right;
                // 将左子树搬到右边
                curr->right = curr->left;
                curr->left = nullptr;
            }
            // 继续处理下一个节点
            curr = curr->right;
        }
    }
};
*/


